κόσκινο του Ερατοσθένη

(Μαθημ.). Ο αλγόριθμος που επινόησε ο αλεξανδρινός μαθηματικός Ερατοσθένης (275-195 π.Χ.) για την εύρεση όλων των πρώτων αριθμών (αριθμοί που διαιρούνται ακριβώς μόνο από τον εαυτό τους και τη μονάδα) από το 1 έως το n (όπου n οποιοσδήποτε φυσικός αριθμός). Κατά τον αλγόριθμο αυτό, χρησιμοποιούνται όλοι οι αριθμοί από το 2 μέχρι και το n και η διαδικασία ξεκινά με το 2 και τη διαγραφή όλων των πολλαπλασίων του. Ύστερα ακολουθεί το 3, όπου και τα πολλαπλάσια αυτού διαγράφονται, στη συνέχεια διαγράφονται τα πολλαπλάσια του 5 (αφού το 4 έχει ήδη διαγραφεί ως πολλαπλάσιο του 2) κ.ο.κ. όσο δεν ξεπερνάται ο αριθμός . Οι αριθμοί που απομένουν στο τέλος είναι οι ζητούμενοι. Πιο αναλυτικά, ο αλγόριθμος έχει τα ακόλουθα τέσσερα βήματα: α) Γραφή με τη σειρά της κύριας λίστας με τους αριθμούς από το 2 μέχρι και το n· β) μεταφορά του πρώτου αριθμού που συναντάται στην κύρια λίστα στη λίστα των πρώτων· γ) διαγραφή όλων των πολλαπλασίων αυτού του αριθμού από την κύρια λίστα· δ) αν ο μικρότερος αριθμός της κύριας λίστας είναι μικρότερος από το ακολουθείται το βήμα 2, αλλιώς όλοι οι εναπομείναντες αριθμοί της κύριας λίστας μεταφέρονται στη λίστα των πρώτων και ο αλγόριθμος τερματίζει. Στο παράδειγμα αυτό προκύπτει ο τρόπος με τον οποίο λειτουργεί το κ. του Ε. για n = 100. Ο αλγόριθμος χρειάζεται τέσσερις επαναλήψεις, για να βρει όλους τους πρώτους αριθμούς από το 1 έως το 100. Κατά την πρώτη επανάληψη λαμβάνεται ο αριθμός 2 και διαγράφονται όλα τα πολλαπλάσιά του. Στη δεύτερη (αντίστοιχα τρίτη) επανάληψη εμφανίζεται ο αριθμός 3 (αντίστοιχα 5) και διαγράφονται όλα τα πολλαπλάσιά του από τους εναπομείναντες αριθμούς. Τέλος στην τέταρτη επανάληψη γίνεται το ίδιο και με το 7, αλλά επειδή = 10 < 11 ο αλγόριθμος τερματίζει. Έτσι, οι πρώτοι αριθμοί από το 1 έως το 100 είναι οι: 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97. Αναπαράσταση του «κόσκινου του Ερατοσθένη». Αναπαράσταση του «κόσκινου του Ερατοσθένη». Αναπαράσταση του «κόσκινου του Ερατοσθένη». Αναπαράσταση του «κόσκινου του Ερατοσθένη». Αναπαράσταση του «κόσκινου του Ερατοσθένη».